package com.yangjiayu.algorithm.array;

/**
 * Leetcode48 旋转图像
 * 旋转一个图片==》 旋转每一个像素点
 *
 */
public class rotateMatrix {


    //矩阵的转置操作A^T
    /*
    1.先转置，再翻转
    1 4 7      7 4 1
    2 5 8  ==> 8 5 2
    3 6 9      9 6 3
     */

    //方法一：数学方法（矩阵转置，再翻转每一行）
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        //1.转置矩阵  对角线上的元素不动 对称元素互换
        for(int i = 0;i<n;i++){
            for(int j = i;j<n;j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        //2.翻转每一行
        for(int i = 0;i<n;i++){
            for(int j = 0;j<n/2;j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n-1-j];
                matrix[i][n-1-j] = temp;
            }
        }


    }

    //方法二：分治思想：分为四个子矩阵分别考虑
    /*
    [1  [2  3]
    4  ]  5  [6
    [7  8]  9]

    四维 （1，0） =》 （0，2） 1 + 2 = n-1

     */
    public void rotate2(int[][] matrix) {
        int n = matrix.length;

        // 遍历四分之一矩阵，左上角
        for(int i = 0;i<n/2 + n%2;i++){//行考虑中间 奇数+1
            for(int j = 0;j<n/2;j++){//列不考虑中间
                //对于matrix[i][j]，需要找到不同的四个矩阵中对应的另外三个位置和元素
                // 定义一个临时数组，保存对应的四个元素
                int[] temp = new int[4];
                int row = i;
                int col = j;
                // 行列转换的规律：row + newCol = n-1 , col = newRow
                for(int k = 0;k<4;k++){
                    temp[k] = matrix[row][col];
                    int x = row;
                    row = col;
                    col = n - 1 - x;
                }

                // 再次遍历要处理的四个位置  将旋转之后的数据填入
                for(int k = 0;k<4;k++){
                    //用上一个值替换当前的位置
                    matrix[row][col] = temp[(k+3)%4];
                    int x = row;
                    row = col;
                    col = n - 1 - x;
                }

            }
        }
    }

    //改进：使用1个临时遍历，不用临时数组
    public void rotate3(int[][] matrix) {
        int n = matrix.length;

        // 遍历四分之一矩阵，左上角
        for(int i = 0;i<(n+1)/2;i++){//行考虑中间 奇数+1
            for(int j = 0;j<n/2;j++){//列不考虑中间
                //对于matrix[i][j]，需要找到不同的四个矩阵中对应的另外三个位置和元素
                int temp = matrix[i][j];
                //找到上一个
                matrix[i][j] = matrix[n-1-j][i];//将上一个位置的元素填入
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[][] image1 = {{1,2,3},{4,5,6},{7,8,9}};
        int[][] image2 = {{5,1,9,11},{2,4,8,10},{13,3,6,7},{15,14,12,16}};
        rotateMatrix rm = new rotateMatrix();
        rm.rotate3(image1);
        rm.rotate3(image2);
        for (int i = 0; i < image1.length; i++) {
            for (int j = 0; j < image1[0].length; j++) {
                System.out.print(image1[i][j]+"\t");
            }
            System.out.println();
        }
        for (int i = 0; i < image2.length; i++) {
            for (int j = 0; j < image2[0].length; j++) {
                System.out.print(image2[i][j]+"\t");
            }
            System.out.println();
        }
    }

}
